package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.Arrays;

/**
 * @author zhangjy
 * @description 从中序与后序遍历序列构造二叉树
 * @date 2025/4/18 17:25
 */
public class BuildTree_106 {

    public static void main(String[] args) {
        BuildTree_106 buildTree106 = new BuildTree_106();

//        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] inorder = new int[]{2, 1};
//        int[] postorder = new int[]{9, 15, 7, 20, 3};
        int[] postorder = new int[]{2, 1};
        TreeNode root = buildTree106.buildTree(inorder, postorder);

        System.out.println(root);
    }

    /**
     * 通过索引下标优化分割
     * <p>
     * TODO 待完善，目前边界处理有问题
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        return dfs2(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    public TreeNode dfs2(int[] inorder, int[] postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
        //
        if (postorderStart < postorderEnd) return null;

        int nodeVal = postorder[postorderEnd];
        TreeNode node = new TreeNode(nodeVal);

        // 叶子节点，直接构造节点并返回
        if (postorderEnd - postorderStart == 0) return node;

        // 1.分割中序
        int pivotInorder = search(nodeVal, inorder);
        // 左闭右闭（分割后的数组下标）
        int inorderLeftStart = inorderStart;
        int inorderLeftEnd = pivotInorder - 1;
        int inorderRightStart = pivotInorder + 1;
        int inorderRightEnd = inorderEnd;

        // 2.分割后序
        int pivotPostorder = inorderLeftEnd - inorderLeftStart;
        int postorderLeftStart = postorderStart;
        int postorderLeftEnd = pivotPostorder;
        int postorderRightStart = pivotInorder + 1;
        int postorderRightEnd = postorderEnd;

        // 左右分组分别向下递归
        TreeNode leftChild = dfs2(inorder, postorder, inorderLeftStart, inorderLeftEnd, postorderLeftStart, postorderLeftEnd);
        TreeNode rightChild = dfs2(inorder, postorder, inorderRightStart, inorderRightEnd, postorderRightStart, postorderRightEnd);

        node.left = leftChild;
        node.right = rightChild;

        return node;
    }

    /**
     * 参考dmsxl：dfs-递归-前序
     * <p>
     * 分析：
     * 1.题目告知节点值都不相同，所以能根据节点值去分割数组。
     * 2.通过中序、后序构造二叉树，就是不断做分割；切割中序、后序选择的基准不同。
     * 3.处理好边界问题，以及每个postorder分组的最后一个元素作为节点值使用过以后，要将其移除。
     * <p>
     * 前序+中序、中序+后序都可以唯一确定二叉树，但是前+后序不能，因为它俩一起无法区分左右。
     * <p>
     * 不足：
     * 耗时又耗空间。
     * 因为，每层递归都定义4个新的数组，并且涉及到数组的复制；可参考官解、dmsxl做优化，每次通过索引下标来分割数组，而不是每次都创建得到分割后的数组。
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 中序数组大小一定是和后序数组的大小相同
        if (inorder.length == 0 || postorder.length == 0) return null;

        int nodeVal = postorder[postorder.length - 1];
        TreeNode node = new TreeNode(nodeVal, null, null);

        // 叶子节点，直接构造节点并返回
        if (postorder.length == 1) return node;

        // 最后一个元素使用后，要移除
        postorder = Arrays.copyOf(postorder, postorder.length - 1);

        int index = search(nodeVal, inorder);
        // 分割中序遍历（左闭右开）
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, index);
        int[] inorderRight = Arrays.copyOfRange(inorder, index + 1, inorder.length);

        // 通过分割的中序，再分割后序（左闭右开）
        // 通过inorderLeft的大小去切；中序、后序左数组的大小相同
        int inorderLeftLength = inorderLeft.length;
        int[] postorderLeft = Arrays.copyOfRange(postorder, 0, inorderLeftLength);
        // postorder已经移除了作为分割点的val对应下标值，所以这里区间为[inorderLeftLength, postorder.length) = [inorderLeftLength, postorder.length - 1]
        // 如果改为分割后，才移除postorder中的val元素，那么右边区间就该变成[inorderLeftLength, postorder.length - 1)
        int[] postorderRight = Arrays.copyOfRange(postorder, inorderLeftLength, postorder.length);

        // 左右分组分别向下递归
        TreeNode leftChild = buildTree(inorderLeft, postorderLeft);
        TreeNode rightChild = buildTree(inorderRight, postorderRight);

        node.left = leftChild;
        node.right = rightChild;

        return node;
    }

    public int search(int val, int[] order) {
        int i = 0, j = order.length - 1;
        while (i < order.length || j > 0) {
            if (order[i] == val) return i;
            if (order[j] == val) return j;

            i++;
            j--;
        }

        // 因为inorder和postorder的元素相同（顺序不同），所以一定不会走到这里
        return -1;
    }

}
